package structure;

/**
 * 二叉树
 */
public class BTree {

    private static Node root;

    public static void add(Node node) {
        Node x = root;
        Node y = null;
        while (x != null) {
            y = x;
            if (node.key < x.key) {
                x = x.l;
            } else {
                x = x.r;
            }
        }
        node.p = y;
        if (y == null) {
            root = node;
        } else if (node.key < y.key) {
            y.l = node;
        } else {
            y.r = node;
        }
    }

    public static void remove(Node x) {
        if (x.l == null) {
            transplant(x, x.r);
        } else if (x.r == null) {
            transplant(x, x.l);
        } else {
            Node sucNode = successor(x);
            if (sucNode.p != x) {
                transplant(sucNode, sucNode.r);
                sucNode.r = x.r;
                sucNode.r.p = sucNode;
            }
            transplant(x, sucNode);
            sucNode.l = x.l;
            sucNode.l.p = sucNode;
        }

    }

    public static void transplant(Node x, Node y) {
        if (x.p == null) {
            root = y;
        } else if (x.p.l == x) {
            x.p.l = y;
        } else {
            x.p.r = y;
        }
        if (y != null) {
            y.p = x.p;
        }
    }

    public static Node successor(Node x) {
        if (x.r != null) {
            return min(x.r);
        }
        while (x.p != null && x == x.p.r) {
            x = x.p;
        }
        return x.p;
    }

    public static Node precursor(Node x) {
        if (x.l != null) {
            return max(x.l);
        }
        if (x.p != null && x.p.l == x) {
            x = x.p;
        }
        return x.p;
    }

    public static Node min(Node x) {
        while (x != null && x.l != null) {
            x = x.l;
        }
        return x;
    }

    public static Node max(Node x) {
        while (x != null && x.r != null) {
            x = x.r;
        }
        return x;
    }

    public static Node search(int key) {
        Node node = root;
        while (node != null) {
            if (key < node.key) {
                node = node.l;
            } else if (key > node.key) {
                node = node.r;
            } else {
                return node;
            }
        }
        return null;
    }

    public static void preorder(Node root) {
        if (root == null) {
            return;
        }
        System.out.println(root.key);
        preorder(root.l);
        preorder(root.r);
    }

    public static void inorder(Node root) {
        if (root == null) {
            return;
        }
        inorder(root.l);
        System.out.println(root.key);
        inorder(root.r);
    }

    public static void postorder(Node node) {
        if (node == null) {
            return;
        }
        postorder(node.l);
        postorder(node.r);
        System.out.println(node.key);
    }

    private static final class Node {
        private Node p;
        private Node l;
        private Node r;
        private int  key;

        public Node getP() {
            return p;
        }

        public void setP(Node p) {
            this.p = p;
        }

        public Node getL() {
            return l;
        }

        public void setL(Node l) {
            this.l = l;
        }

        public Node getR() {
            return r;
        }

        public void setR(Node r) {
            this.r = r;
        }

        public int getKey() {
            return key;
        }

        public void setKey(int key) {
            this.key = key;
        }
    }
}
